1. Field of the Invention
This invention relates to image compression methodologies and more particularly, to an apparatus and method for compression of still images
2. Prior Art
Still image compression techniques have been improvised and improved significantly over the past ten years to envelop highly specialized algorithms and mathematical techniques in order to increase the compression ratio of the image. This has been especially the case in recent years as transmission of digital images, particularly color images, over computer networks or telephone lines is highly demanded by consumers. Particularly, transmission of these color images at high speed is desired. In order to increase the speed of transmission for the digitized color image, compression of the image is required. There has been traditionally a trade off between compression and quality however, requiring that the developer of compression techniques and apparatus choose between high compression ratios and therefor increased transmission speeds against the quality of the image once it is decompressed to its initial, or quasi-initial appearance. Inherent in most compression techniques are tradeoffs wherein, particular aspects of the image are sacrificed in order to compress the image to a satisfactory size. These losses of data can include loss of color definition, sharpness of edge lines, or other aspects of image quality. This sacrifice of image quality, particularly for color images, comes at high costs, particularly when the typical compression ratio achieved is less than 20 to 1.
Standard image compression techniques include the following methodology: 
In the Digital Conversion of Image step, a CMYK, CMY or Postscript image is scanned and prepared in digital format which most likely includes representing the image in RGB or YUV components. RGB and YUV formatting allows the color image to be broken down into distinct color spectrums or luminance and then compressed based upon those spectrums. After reducing the image to particular color or luminance components, the components may be broken down into blocks of pixels for easy manipulation and analysis.
The next typical step involves generating the matrix transform wherein the image, in its component form, is transformed form one domain to another. This allows the image to be removed from the standard two dimensional image space to the frequency domain thereby causing the coefficients created to be the target of the compression routines and not the color component values themselves. The Discrete Cosine Transform or Fourier Transforms (transforms based upon a linear combinatory of sine and cosine waves with different coefficients) are used to convert the image data to the frequency domain and create the coefficient matrix. These transforms indicate the behavior in the frequency domain of the image as such, they are typically well for homogeneous image areas. The resulting transform coefficients are then compressed by possibly thresholding and also through quantization routines. Quantization may reduce the precision of the coefficients generated in the transform step but allows the actual values to be compressed. This quantization step scales the coefficients by a step size and then rounds off the value to the next integer. Finally, entropy or source encoding is utilized to further compress the quantized data. This encoding step may include run length encoding, Lempel-Ziv-Welch, Huffman, DCPM (differential pulse code modulation) or other well known coding techniques.
More recently, Fourier or DCT transformation matrices have been replaced with more complicated Wavelet transforms. As two types of compression models, lossy coding and lossless coding, have become standard, Wavelet transforms have provided a means to significantly increase compression ratios for the lossless type of compression model. In a lossless type of compression model, the input data, typically intensity data, is converted to codewords which have fewer storage requirements than the data that is coded. In the lossy model, intensity data may be quantized prior to utilization of codewords or transformation. Quantization eliminates those data elements which are not considered relevant to the characteristics of the image. Prior to the quantization step in lossy compression models, transforms are typically utilized to compress the data prior to action upon it by quantization routines.
Wavelet transforms are based on a linear combination of waveforms that are not periodic but display a strong locality, i.e. the local specifics of the image. In wavelet transformations, unlike in a DCT transformation matrix, the image is transformed as a whole, not in modularized pixel blocks. A set of dependent functions are derived from a prototype function each of which have fundamental characteristics for transformation of the data (i.e. scale and transform) such that tradeoffs may be made based upon application specific requirements. These tradeoffs flow from resolution in the time and frequency domain. The dependent functions may be scaled and transformed to meet the requirements of a particular application. Scaling and transformation coefficients are similar to the DCT coefficients. The varying dependent functions allow tradeoffs between the frequency and time resolution. As a result of these wavelet transforms, the high and low frequency portions of the image will be processed independently thus allowing the wavelet functions to act as band pass filters. Each of these filtered signals may then be further separated into various average signals and horizontal, vertical and diagonal features.
Filtering of the image in the horizontal, vertical and diagonal direction may be accomplished to produce separate images through use of high and low filter pass techniques along with an average image signal. Iterative passes may be made to further compress the image thereby producing coefficients for each image which may then be compressed further through encoding or other methods mentioned above. All of these techniques utilize data transform methodology function.
Representation of data using a set of basis functions is well known, with Fourier techniques being perhaps the most familiar. Other transform methods include the fast Fourier transform (FFT), the discrete cosine transform (DCT), and a variety of wavelet transforms. The rationalization for such transform methods is that the basis functions can be encoded by coefficient values and that certain coefficients may be treated as more significant than others based on the information content of the original source data. In doing so, they effectively regard certain coefficient values and correlations of the sort mimicked by the basis functions as more important than any other values or correlations. In essence, transform methods are a means of categorizing the correlations in an image. The limitations of such methods are a result of the unpredictability of the correlations. The variations in luminance and color that characterize an image are often localized and change across the face of the image. As a result, FFT and DCT based methods, such as JPEG, often first segment an image into a number of blocks so that the analysis of correlations can be restricted to a small area of the image. A consequence of this approach is that bothersome discontinuities can occur at the edges of the blocks.
Historical wavelet-based methods avoid this xe2x80x9cblocking effectxe2x80x9d somewhat by using basis functions that are more localized than sine and cosine functions. However, a problem with these historical wavelet-based methods is that they assume that a particular function is appropriate for an image and that the entire image may be described by the superposition of scaled versions of that function centered at different places within the image. Given the complexity of image data, such a presumption is often unjustified. Consequently, historical wavelet based methods tend to produce textural blurring and noticeable changes in processing and coding quality within and between images
These standard compression techniques may cause significant degradation in the uncompressed image due to the varying manipulations to color, luminance and loss of data during the compression routine. Thus, it is standard to see visually optimized transformation matrices or quantization steps which attempt to reduce the amount of data loss during the compression transformation. These errors may be further enhanced by the initial transformation of the color image from standard color high definition matrix to an RGB or YUV matrix. All of these data manipulations reduce the quality of the decompressed image while achieving relatively low compression ratios.
One object of the present invention is to devise a compression algorithm for color images which achieves large compression ratios and wherein the detection of errors from the compression and decompression step is negligible. Another object of the present invention is to provide a color image compression routine which works on the standard CMYK color space and does not require conversion of the color data form standard color to RGB color representation. A third object of the present invention is to provide transformation algorithms which will not overburden a hardware system designed to compress and decompress the images thereby allowing high compression and decompression speeds through the use of efficient compression methodologies and standard electronics.
Image compression algorithms created so far for CMYK, CMY and PostScript still image convert the data to RGB then compress the RGB image data and subsequently convert back to CMYK, or CMY, or PostScript. Furthermore, the prior art typically uses the same transformation for the horizontal and vertical directions.
The image compression system of the present invention includes several novel features; First, the system of the present invention does not transfer to the RGB color space for compression but operates directly on the CMYK color space or PostScript space. The second feature is that the size of the filter transformation depends on the zone of influence of the autocorrelation function.
The third novel feature of the present invention is that the present technique treats the horizontal and vertical directions differently depending on the aspect ratio and the anisotropic behavior of the autocorrelation function in the vertical and horizontal directions. Due to the fact that the aspect ratio of the horizontal and vertical pixels is usually not equal to one, and also due to the fact that the zone of influence of the autocorrelation function in the horizontal direction is not equal to the zone of influence of the autocorrelation function in the vertical direction, it is more efficient to use a different filter size in the horizontal direction than in the vertical direction.
The optimal filter size is computed mathematically so that conversion of the floating point data obtained by the transformation from the space domain to the frequency domain from floating points to integer numbers produces relatively small error. This error is bounded by a predefined value which represents the worse case analysis error and therefore produces pixels that are either identical to the corresponding pixels of the original image or they are very close to the pixels of the original image. The difference of the corresponding pixels of the original image and the restored image are bounded by the desired error boundary chosen so that the quality of the restored image is very high and therefore no visible differences exist between the original image and the restored image. The transformations are designed to divide the image signal into disjoint frequency bands. Each band has different amount of energy. The sum of a small number of bands carries over 99% of the energy of the image signal.
The fourth innovation of the present invention is that the quantization step is directional and band dependent. The quantizer is designed so that it will not quantize the frequency bands where the energy of the system is relatively high. Alternatively, the frequency bands with relatively low energy are quantized inversely proportional to their variance. The error produced from this quantization as well as the error produced by the rounding off of the frequency domain is designed to produce a decompressed image with pixels having maximum distance from the corresponding pixels of the original image which is less than a desired error boundary. Therefor when the image is compressed and subsequently decompressed, the error produced is too small for the eye to detect. Thus, a printout of the original image and the restored image looks identical to the eye.